Left Termination of the query pattern
f(g,g,a)
w.r.t. the given Prolog program could successfully be proven:

(0) Obligation:

Clauses:

f(A, [], RES) :- g(A, [], RES).
f(.(A, As), .(B, Bs), RES) :- f(.(B, .(A, As)), Bs, RES).
g([], RES, RES).
g(.(C, Cs), D, RES) :- g(Cs, .(C, D), RES).

Query: f(g,g,a)

(1) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph DT10.

digraph dp_graph {
node [outthreshold=100, inthreshold=100];
1 [label="C: f(T1, T2, T3)\n\nT1 is ground\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow, color=red];
2 [label="2: f(T1, T2, T3), SCOPE: 1, CLAUSE: 0 | f(T1, T2, T3), SCOPE: 1, CLAUSE: 1\n\nT1 is ground\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
3 [label="3: g(T6, [], T8) | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
4 [label="4: f(T1, T2, T3), SCOPE: 1, CLAUSE: 1\n\nT1 is ground\nT2 is ground\nX3 is free\nX4 is free\nf(T1, T2, T3) !=? f(X3, [], X4)", fontsize=16, style=filled, fillcolor=lightyellow];
5 [label="5: g(T6, [], T8), SCOPE: 2, CLAUSE: 2 | g(T6, [], T8), SCOPE: 2, CLAUSE: 3 | ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
6 [label="6: g(T6, [], T8), SCOPE: 2, CLAUSE: 2\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
7 [label="7: g(T6, [], T8), SCOPE: 2, CLAUSE: 3 | ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
8 [label="8: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
9 [label="9: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
10 [label="10: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
11 [label="11: g(T6, [], T8), SCOPE: 2, CLAUSE: 3\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
12 [label="12: ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
13 [label="B: g(T22, .(T21, []), T24)\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
14 [label="14: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
15 [label="15: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 2 | g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 3\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
16 [label="16: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 2\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
17 [label="17: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 3\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
18 [label="18: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
19 [label="19: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
20 [label="20: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
21 [label="21: g(T41, .(T40, .(T42, [])), T44)\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
22 [label="22: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
23 [label="23: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 2 | g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 3\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
24 [label="24: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 2\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
25 [label="25: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 3\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
26 [label="26: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
27 [label="27: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
28 [label="28: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
29 [label="29: g(T70, .(T69, .(T71, .(T72, []))), T74)\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
30 [label="30: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
31 [label="31: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 2 | g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 3\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
32 [label="32: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 2\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
33 [label="33: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 3\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
34 [label="34: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
35 [label="35: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
36 [label="36: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
37 [label="37: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114)\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
38 [label="38: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
39 [label="39: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 2 | g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 3\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
40 [label="40: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 2\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
41 [label="41: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 3\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
42 [label="42: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
43 [label="43: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
44 [label="44: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
45 [label="45: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164)\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
46 [label="46: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
47 [label="47: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 2 | g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 3\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
48 [label="48: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 2\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
49 [label="49: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 3\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
50 [label="50: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
51 [label="51: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
52 [label="52: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
53 [label="53: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224)\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
54 [label="54: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
55 [label="55: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 2 | g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 3\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
56 [label="56: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 2\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
57 [label="57: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 3\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
58 [label="58: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
59 [label="59: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
60 [label="60: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
61 [label="61: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294)\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
62 [label="62: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
63 [label="63: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 2 | g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 3\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
64 [label="64: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 2\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
65 [label="65: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 3\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
66 [label="66: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
67 [label="67: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
68 [label="68: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
69 [label="69: g(T365, .(T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, [])))))))), T374)\n\nT364 is ground\nT365 is ground\nT366 is ground\nT367 is ground\nT368 is ground\nT369 is ground\nT370 is ground\nT371 is ground\nT372 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
70 [label="70: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
71 [label="A: g(T365, .(T364, T391), T374)\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
72 [label="72: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 2 | g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 3\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
73 [label="73: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 2\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
74 [label="74: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 3\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
75 [label="75: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
76 [label="76: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
77 [label="77: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
78 [label="78: g(T417, .(T416, .(T418, T419)), T421)\n\nT416 is ground\nT417 is ground\nT418 is ground\nT419 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
79 [label="79: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
80 [label="80: f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
81 [label="81: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
82 [label="82: f(.(T437, .(T435, T436)), T438, T440)\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
83 [label="83: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
84 [label="84: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 0 | f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 1\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
85 [label="85: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 0\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
86 [label="86: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 1\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
87 [label="87: g(.(T457, .(T458, T459)), [], T461)\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
88 [label="88: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
89 [label="89: g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 2 | g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 3\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
90 [label="90: g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 3\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
91 [label="91: g(.(T472, T473), .(T471, []), T475)\n\nT471 is ground\nT472 is ground\nT473 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
92 [label="92: f(.(T491, .(T488, .(T489, T490))), T492, T494)\n\nT488 is ground\nT489 is ground\nT490 is ground\nT491 is ground\nT492 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
93 [label="93: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
94 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
1 -> 94 [arrowhead = none ];
94 -> 2;

95 [label="EVAL with clause\nf(X3, [], X4) :- g(X3, [], X4).\nand substitutionT1 -> T6,\nX3 -> T6,\nT2 -> [],\nT3 -> T8,\nX4 -> T8,\nT7 -> T8", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 95 [arrowhead = none ];
95 -> 3;

96 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
2 -> 96 [arrowhead = none ];
96 -> 4;

97 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
3 -> 97 [arrowhead = none ];
97 -> 5;

98 [label="EVAL with clause\nf(.(X196, X197), .(X198, X199), X200) :- f(.(X198, .(X196, X197)), X199, X200).\nand substitutionX196 -> T435,\nX197 -> T436,\nT1 -> .(T435, T436),\nX198 -> T437,\nX199 -> T438,\nT2 -> .(T437, T438),\nT3 -> T440,\nX200 -> T440,\nT439 -> T440", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 98 [arrowhead = none ];
98 -> 82;

99 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
4 -> 99 [arrowhead = none ];
99 -> 83;

100 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
5 -> 100 [arrowhead = none ];
100 -> 6;

101 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
5 -> 101 [arrowhead = none ];
101 -> 7;

102 [label="EVAL with clause\ng([], X9, X9).\nand substitutionT6 -> [],\nX9 -> [],\nT8 -> []", fontsize=14, style = filled, fillcolor = lightblue];
6 -> 102 [arrowhead = none ];
102 -> 8;

103 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
6 -> 103 [arrowhead = none ];
103 -> 9;

104 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
7 -> 104 [arrowhead = none ];
104 -> 11;

105 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
7 -> 105 [arrowhead = none ];
105 -> 12;

106 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
8 -> 106 [arrowhead = none ];
106 -> 10;

107 [label="EVAL with clause\ng(.(X26, X27), X28, X29) :- g(X27, .(X26, X28), X29).\nand substitutionX26 -> T21,\nX27 -> T22,\nT6 -> .(T21, T22),\nX28 -> [],\nT8 -> T24,\nX29 -> T24,\nT23 -> T24", fontsize=14, style = filled, fillcolor = lightblue];
11 -> 107 [arrowhead = none ];
107 -> 13;

108 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
11 -> 108 [arrowhead = none ];
108 -> 14;

109 [label="FAILURE", fontsize=14, style = filled, fillcolor = lightgreen];
12 -> 109 [arrowhead = none ];
109 -> 80;

110 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
13 -> 110 [arrowhead = none ];
110 -> 15;

111 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
15 -> 111 [arrowhead = none ];
111 -> 16;

112 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
15 -> 112 [arrowhead = none ];
112 -> 17;

113 [label="EVAL with clause\ng([], X36, X36).\nand substitutionT22 -> [],\nT21 -> T31,\nX36 -> .(T31, []),\nT24 -> .(T31, [])", fontsize=14, style = filled, fillcolor = lightblue];
16 -> 113 [arrowhead = none ];
113 -> 18;

114 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
16 -> 114 [arrowhead = none ];
114 -> 19;

115 [label="EVAL with clause\ng(.(X45, X46), X47, X48) :- g(X46, .(X45, X47), X48).\nand substitutionX45 -> T40,\nX46 -> T41,\nT22 -> .(T40, T41),\nT21 -> T42,\nX47 -> .(T42, []),\nT24 -> T44,\nX48 -> T44,\nT43 -> T44", fontsize=14, style = filled, fillcolor = lightblue];
17 -> 115 [arrowhead = none ];
115 -> 21;

116 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
17 -> 116 [arrowhead = none ];
116 -> 22;

117 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
18 -> 117 [arrowhead = none ];
117 -> 20;

118 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
21 -> 118 [arrowhead = none ];
118 -> 23;

119 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
23 -> 119 [arrowhead = none ];
119 -> 24;

120 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
23 -> 120 [arrowhead = none ];
120 -> 25;

121 [label="EVAL with clause\ng([], X55, X55).\nand substitutionT41 -> [],\nT40 -> T57,\nT42 -> T58,\nX55 -> .(T57, .(T58, [])),\nT44 -> .(T57, .(T58, []))", fontsize=14, style = filled, fillcolor = lightblue];
24 -> 121 [arrowhead = none ];
121 -> 26;

122 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
24 -> 122 [arrowhead = none ];
122 -> 27;

123 [label="EVAL with clause\ng(.(X64, X65), X66, X67) :- g(X65, .(X64, X66), X67).\nand substitutionX64 -> T69,\nX65 -> T70,\nT41 -> .(T69, T70),\nT40 -> T71,\nT42 -> T72,\nX66 -> .(T71, .(T72, [])),\nT44 -> T74,\nX67 -> T74,\nT73 -> T74", fontsize=14, style = filled, fillcolor = lightblue];
25 -> 123 [arrowhead = none ];
123 -> 29;

124 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
25 -> 124 [arrowhead = none ];
124 -> 30;

125 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
26 -> 125 [arrowhead = none ];
125 -> 28;

126 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
29 -> 126 [arrowhead = none ];
126 -> 31;

127 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
31 -> 127 [arrowhead = none ];
127 -> 32;

128 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
31 -> 128 [arrowhead = none ];
128 -> 33;

129 [label="EVAL with clause\ng([], X74, X74).\nand substitutionT70 -> [],\nT69 -> T93,\nT71 -> T94,\nT72 -> T95,\nX74 -> .(T93, .(T94, .(T95, []))),\nT74 -> .(T93, .(T94, .(T95, [])))", fontsize=14, style = filled, fillcolor = lightblue];
32 -> 129 [arrowhead = none ];
129 -> 34;

130 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
32 -> 130 [arrowhead = none ];
130 -> 35;

131 [label="EVAL with clause\ng(.(X83, X84), X85, X86) :- g(X84, .(X83, X85), X86).\nand substitutionX83 -> T108,\nX84 -> T109,\nT70 -> .(T108, T109),\nT69 -> T110,\nT71 -> T111,\nT72 -> T112,\nX85 -> .(T110, .(T111, .(T112, []))),\nT74 -> T114,\nX86 -> T114,\nT113 -> T114", fontsize=14, style = filled, fillcolor = lightblue];
33 -> 131 [arrowhead = none ];
131 -> 37;

132 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
33 -> 132 [arrowhead = none ];
132 -> 38;

133 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
34 -> 133 [arrowhead = none ];
133 -> 36;

134 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
37 -> 134 [arrowhead = none ];
134 -> 39;

135 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
39 -> 135 [arrowhead = none ];
135 -> 40;

136 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
39 -> 136 [arrowhead = none ];
136 -> 41;

137 [label="EVAL with clause\ng([], X93, X93).\nand substitutionT109 -> [],\nT108 -> T139,\nT110 -> T140,\nT111 -> T141,\nT112 -> T142,\nX93 -> .(T139, .(T140, .(T141, .(T142, [])))),\nT114 -> .(T139, .(T140, .(T141, .(T142, []))))", fontsize=14, style = filled, fillcolor = lightblue];
40 -> 137 [arrowhead = none ];
137 -> 42;

138 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
40 -> 138 [arrowhead = none ];
138 -> 43;

139 [label="EVAL with clause\ng(.(X102, X103), X104, X105) :- g(X103, .(X102, X104), X105).\nand substitutionX102 -> T157,\nX103 -> T158,\nT109 -> .(T157, T158),\nT108 -> T159,\nT110 -> T160,\nT111 -> T161,\nT112 -> T162,\nX104 -> .(T159, .(T160, .(T161, .(T162, [])))),\nT114 -> T164,\nX105 -> T164,\nT163 -> T164", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 139 [arrowhead = none ];
139 -> 45;

140 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
41 -> 140 [arrowhead = none ];
140 -> 46;

141 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
42 -> 141 [arrowhead = none ];
141 -> 44;

142 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
45 -> 142 [arrowhead = none ];
142 -> 47;

143 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
47 -> 143 [arrowhead = none ];
143 -> 48;

144 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
47 -> 144 [arrowhead = none ];
144 -> 49;

145 [label="EVAL with clause\ng([], X112, X112).\nand substitutionT158 -> [],\nT157 -> T195,\nT159 -> T196,\nT160 -> T197,\nT161 -> T198,\nT162 -> T199,\nX112 -> .(T195, .(T196, .(T197, .(T198, .(T199, []))))),\nT164 -> .(T195, .(T196, .(T197, .(T198, .(T199, [])))))", fontsize=14, style = filled, fillcolor = lightblue];
48 -> 145 [arrowhead = none ];
145 -> 50;

146 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
48 -> 146 [arrowhead = none ];
146 -> 51;

147 [label="EVAL with clause\ng(.(X121, X122), X123, X124) :- g(X122, .(X121, X123), X124).\nand substitutionX121 -> T216,\nX122 -> T217,\nT158 -> .(T216, T217),\nT157 -> T218,\nT159 -> T219,\nT160 -> T220,\nT161 -> T221,\nT162 -> T222,\nX123 -> .(T218, .(T219, .(T220, .(T221, .(T222, []))))),\nT164 -> T224,\nX124 -> T224,\nT223 -> T224", fontsize=14, style = filled, fillcolor = lightblue];
49 -> 147 [arrowhead = none ];
147 -> 53;

148 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
49 -> 148 [arrowhead = none ];
148 -> 54;

149 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
50 -> 149 [arrowhead = none ];
149 -> 52;

150 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
53 -> 150 [arrowhead = none ];
150 -> 55;

151 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 151 [arrowhead = none ];
151 -> 56;

152 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 152 [arrowhead = none ];
152 -> 57;

153 [label="EVAL with clause\ng([], X131, X131).\nand substitutionT217 -> [],\nT216 -> T261,\nT218 -> T262,\nT219 -> T263,\nT220 -> T264,\nT221 -> T265,\nT222 -> T266,\nX131 -> .(T261, .(T262, .(T263, .(T264, .(T265, .(T266, [])))))),\nT224 -> .(T261, .(T262, .(T263, .(T264, .(T265, .(T266, []))))))", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 153 [arrowhead = none ];
153 -> 58;

154 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
56 -> 154 [arrowhead = none ];
154 -> 59;

155 [label="EVAL with clause\ng(.(X140, X141), X142, X143) :- g(X141, .(X140, X142), X143).\nand substitutionX140 -> T285,\nX141 -> T286,\nT217 -> .(T285, T286),\nT216 -> T287,\nT218 -> T288,\nT219 -> T289,\nT220 -> T290,\nT221 -> T291,\nT222 -> T292,\nX142 -> .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, [])))))),\nT224 -> T294,\nX143 -> T294,\nT293 -> T294", fontsize=14, style = filled, fillcolor = lightblue];
57 -> 155 [arrowhead = none ];
155 -> 61;

156 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
57 -> 156 [arrowhead = none ];
156 -> 62;

157 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
58 -> 157 [arrowhead = none ];
157 -> 60;

158 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
61 -> 158 [arrowhead = none ];
158 -> 63;

159 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
63 -> 159 [arrowhead = none ];
159 -> 64;

160 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
63 -> 160 [arrowhead = none ];
160 -> 65;

161 [label="EVAL with clause\ng([], X150, X150).\nand substitutionT286 -> [],\nT285 -> T337,\nT287 -> T338,\nT288 -> T339,\nT289 -> T340,\nT290 -> T341,\nT291 -> T342,\nT292 -> T343,\nX150 -> .(T337, .(T338, .(T339, .(T340, .(T341, .(T342, .(T343, []))))))),\nT294 -> .(T337, .(T338, .(T339, .(T340, .(T341, .(T342, .(T343, [])))))))", fontsize=14, style = filled, fillcolor = lightblue];
64 -> 161 [arrowhead = none ];
161 -> 66;

162 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
64 -> 162 [arrowhead = none ];
162 -> 67;

163 [label="EVAL with clause\ng(.(X159, X160), X161, X162) :- g(X160, .(X159, X161), X162).\nand substitutionX159 -> T364,\nX160 -> T365,\nT286 -> .(T364, T365),\nT285 -> T366,\nT287 -> T367,\nT288 -> T368,\nT289 -> T369,\nT290 -> T370,\nT291 -> T371,\nT292 -> T372,\nX161 -> .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))),\nT294 -> T374,\nX162 -> T374,\nT373 -> T374", fontsize=14, style = filled, fillcolor = lightblue];
65 -> 163 [arrowhead = none ];
163 -> 69;

164 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
65 -> 164 [arrowhead = none ];
164 -> 70;

165 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
66 -> 165 [arrowhead = none ];
165 -> 68;

166 [label="GENERALIZATION\nT391 <-- .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, [])))))))\n\nNew Knowledge:\nT391 is ground", fontsize=14, style = filled, fillcolor = violet];
69 -> 166 [arrowhead = none ];
166 -> 71;

167 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
71 -> 167 [arrowhead = none ];
167 -> 72;

168 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
72 -> 168 [arrowhead = none ];
168 -> 73;

169 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
72 -> 169 [arrowhead = none ];
169 -> 74;

170 [label="EVAL with clause\ng([], X171, X171).\nand substitutionT365 -> [],\nT364 -> T404,\nT391 -> T405,\nX171 -> .(T404, T405),\nT374 -> .(T404, T405)", fontsize=14, style = filled, fillcolor = lightblue];
73 -> 170 [arrowhead = none ];
170 -> 75;

171 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
73 -> 171 [arrowhead = none ];
171 -> 76;

172 [label="EVAL with clause\ng(.(X180, X181), X182, X183) :- g(X181, .(X180, X182), X183).\nand substitutionX180 -> T416,\nX181 -> T417,\nT365 -> .(T416, T417),\nT364 -> T418,\nT391 -> T419,\nX182 -> .(T418, T419),\nT374 -> T421,\nX183 -> T421,\nT420 -> T421", fontsize=14, style = filled, fillcolor = lightblue];
74 -> 172 [arrowhead = none ];
172 -> 78;

173 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
74 -> 173 [arrowhead = none ];
173 -> 79;

174 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
75 -> 174 [arrowhead = none ];
174 -> 77;

175 [label="INSTANCE with matching:\nT365 -> T417\nT364 -> T416\nT391 -> .(T418, T419)\nT374 -> T421", fontsize=14, style = filled, fillcolor = lightgrey];
78 -> 175 [arrowhead = none , style=dashed];
175 -> 71[style=dashed];

176 [label="BACKTRACK\nfor clause: f(.(A, As), .(B, Bs), RES) :- f(.(B, .(A, As)), Bs, RES)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
80 -> 176 [arrowhead = none ];
176 -> 81;

177 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
82 -> 177 [arrowhead = none ];
177 -> 84;

178 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
84 -> 178 [arrowhead = none ];
178 -> 85;

179 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
84 -> 179 [arrowhead = none ];
179 -> 86;

180 [label="EVAL with clause\nf(X209, [], X210) :- g(X209, [], X210).\nand substitutionT437 -> T457,\nT435 -> T458,\nT436 -> T459,\nX209 -> .(T457, .(T458, T459)),\nT438 -> [],\nT440 -> T461,\nX210 -> T461,\nT460 -> T461", fontsize=14, style = filled, fillcolor = lightblue];
85 -> 180 [arrowhead = none ];
180 -> 87;

181 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
85 -> 181 [arrowhead = none ];
181 -> 88;

182 [label="EVAL with clause\nf(.(X240, X241), .(X242, X243), X244) :- f(.(X242, .(X240, X241)), X243, X244).\nand substitutionT437 -> T488,\nX240 -> T488,\nT435 -> T489,\nT436 -> T490,\nX241 -> .(T489, T490),\nX242 -> T491,\nX243 -> T492,\nT438 -> .(T491, T492),\nT440 -> T494,\nX244 -> T494,\nT493 -> T494", fontsize=14, style = filled, fillcolor = lightblue];
86 -> 182 [arrowhead = none ];
182 -> 92;

183 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
86 -> 183 [arrowhead = none ];
183 -> 93;

184 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
87 -> 184 [arrowhead = none ];
184 -> 89;

185 [label="BACKTRACK\nfor clause: g([], RES, RES)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
89 -> 185 [arrowhead = none ];
185 -> 90;

186 [label="ONLY EVAL with clause\ng(.(X224, X225), X226, X227) :- g(X225, .(X224, X226), X227).\nand substitutionT457 -> T471,\nX224 -> T471,\nT458 -> T472,\nT459 -> T473,\nX225 -> .(T472, T473),\nX226 -> [],\nT461 -> T475,\nX227 -> T475,\nT474 -> T475", fontsize=14, style = filled, fillcolor = lightblue];
90 -> 186 [arrowhead = none ];
186 -> 91;

187 [label="INSTANCE with matching:\nT22 -> .(T472, T473)\nT21 -> T471\nT24 -> T475", fontsize=14, style = filled, fillcolor = lightgrey];
91 -> 187 [arrowhead = none , style=dashed];
187 -> 13[style=dashed];

188 [label="INSTANCE with matching:\nT1 -> .(T491, .(T488, .(T489, T490)))\nT2 -> T492\nT3 -> T494", fontsize=14, style = filled, fillcolor = lightgrey];
92 -> 188 [arrowhead = none , style=dashed];
188 -> 1[style=dashed];

}

(2) Obligation:

Triples:

gA(.(X1, X2), X3, X4, X5) :- gA(X2, X1, .(X3, X4), X5).
gB(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) :- gA(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10).
fC(.(X1, X2), [], X3) :- gB(X2, X1, X3).
fC(.(X1, X2), .(X3, []), X4) :- gB(.(X1, X2), X3, X4).
fC(.(X1, X2), .(X3, .(X4, X5)), X6) :- fC(.(X4, .(X3, .(X1, X2))), X5, X6).

Clauses:

gcA([], X1, X2, .(X1, X2)).
gcA(.(X1, X2), X3, X4, X5) :- gcA(X2, X1, .(X3, X4), X5).
gcB([], X1, .(X1, [])).
gcB(.(X1, []), X2, .(X1, .(X2, []))).
gcB(.(X1, .(X2, [])), X3, .(X2, .(X1, .(X3, [])))).
gcB(.(X1, .(X2, .(X3, []))), X4, .(X3, .(X2, .(X1, .(X4, []))))).
gcB(.(X1, .(X2, .(X3, .(X4, [])))), X5, .(X4, .(X3, .(X2, .(X1, .(X5, [])))))).
gcB(.(X1, .(X2, .(X3, .(X4, .(X5, []))))), X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X6, []))))))).
gcB(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, [])))))), X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X7, [])))))))).
gcB(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) :- gcA(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10).
fcC([], [], []).
fcC(.(X1, X2), [], X3) :- gcB(X2, X1, X3).
fcC(.(X1, X2), .(X3, []), X4) :- gcB(.(X1, X2), X3, X4).
fcC(.(X1, X2), .(X3, .(X4, X5)), X6) :- fcC(.(X4, .(X3, .(X1, X2))), X5, X6).

Afs:

fC(x1, x2, x3)  =  fC(x1, x2)

(3) TriplesToPiDPProof (SOUND transformation)

We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
fC_in: (b,b,f)
gB_in: (b,b,f)
gA_in: (b,b,b,f)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

FC_IN_GGA(.(X1, X2), [], X3) → U3_GGA(X1, X2, X3, gB_in_gga(X2, X1, X3))
FC_IN_GGA(.(X1, X2), [], X3) → GB_IN_GGA(X2, X1, X3)
GB_IN_GGA(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) → U2_GGA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, gA_in_ggga(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10))
GB_IN_GGA(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) → GA_IN_GGGA(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10)
GA_IN_GGGA(.(X1, X2), X3, X4, X5) → U1_GGGA(X1, X2, X3, X4, X5, gA_in_ggga(X2, X1, .(X3, X4), X5))
GA_IN_GGGA(.(X1, X2), X3, X4, X5) → GA_IN_GGGA(X2, X1, .(X3, X4), X5)
FC_IN_GGA(.(X1, X2), .(X3, []), X4) → U4_GGA(X1, X2, X3, X4, gB_in_gga(.(X1, X2), X3, X4))
FC_IN_GGA(.(X1, X2), .(X3, []), X4) → GB_IN_GGA(.(X1, X2), X3, X4)
FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5)), X6) → U5_GGA(X1, X2, X3, X4, X5, X6, fC_in_gga(.(X4, .(X3, .(X1, X2))), X5, X6))
FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5)), X6) → FC_IN_GGA(.(X4, .(X3, .(X1, X2))), X5, X6)

R is empty.
The argument filtering Pi contains the following mapping:
fC_in_gga(x1, x2, x3)  =  fC_in_gga(x1, x2)
.(x1, x2)  =  .(x1, x2)
[]  =  []
gB_in_gga(x1, x2, x3)  =  gB_in_gga(x1, x2)
gA_in_ggga(x1, x2, x3, x4)  =  gA_in_ggga(x1, x2, x3)
FC_IN_GGA(x1, x2, x3)  =  FC_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
GB_IN_GGA(x1, x2, x3)  =  GB_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)  =  U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x11)
GA_IN_GGGA(x1, x2, x3, x4)  =  GA_IN_GGGA(x1, x2, x3)
U1_GGGA(x1, x2, x3, x4, x5, x6)  =  U1_GGGA(x1, x2, x3, x4, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5, x6, x7)  =  U5_GGA(x1, x2, x3, x4, x5, x7)

We have to consider all (P,R,Pi)-chains

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(4) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

FC_IN_GGA(.(X1, X2), [], X3) → U3_GGA(X1, X2, X3, gB_in_gga(X2, X1, X3))
FC_IN_GGA(.(X1, X2), [], X3) → GB_IN_GGA(X2, X1, X3)
GB_IN_GGA(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) → U2_GGA(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, gA_in_ggga(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10))
GB_IN_GGA(.(X1, .(X2, .(X3, .(X4, .(X5, .(X6, .(X7, X8))))))), X9, X10) → GA_IN_GGGA(X8, X7, .(X6, .(X5, .(X4, .(X3, .(X2, .(X1, .(X9, []))))))), X10)
GA_IN_GGGA(.(X1, X2), X3, X4, X5) → U1_GGGA(X1, X2, X3, X4, X5, gA_in_ggga(X2, X1, .(X3, X4), X5))
GA_IN_GGGA(.(X1, X2), X3, X4, X5) → GA_IN_GGGA(X2, X1, .(X3, X4), X5)
FC_IN_GGA(.(X1, X2), .(X3, []), X4) → U4_GGA(X1, X2, X3, X4, gB_in_gga(.(X1, X2), X3, X4))
FC_IN_GGA(.(X1, X2), .(X3, []), X4) → GB_IN_GGA(.(X1, X2), X3, X4)
FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5)), X6) → U5_GGA(X1, X2, X3, X4, X5, X6, fC_in_gga(.(X4, .(X3, .(X1, X2))), X5, X6))
FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5)), X6) → FC_IN_GGA(.(X4, .(X3, .(X1, X2))), X5, X6)

R is empty.
The argument filtering Pi contains the following mapping:
fC_in_gga(x1, x2, x3)  =  fC_in_gga(x1, x2)
.(x1, x2)  =  .(x1, x2)
[]  =  []
gB_in_gga(x1, x2, x3)  =  gB_in_gga(x1, x2)
gA_in_ggga(x1, x2, x3, x4)  =  gA_in_ggga(x1, x2, x3)
FC_IN_GGA(x1, x2, x3)  =  FC_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
GB_IN_GGA(x1, x2, x3)  =  GB_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)  =  U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x11)
GA_IN_GGGA(x1, x2, x3, x4)  =  GA_IN_GGGA(x1, x2, x3)
U1_GGGA(x1, x2, x3, x4, x5, x6)  =  U1_GGGA(x1, x2, x3, x4, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5, x6, x7)  =  U5_GGA(x1, x2, x3, x4, x5, x7)

We have to consider all (P,R,Pi)-chains

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

GA_IN_GGGA(.(X1, X2), X3, X4, X5) → GA_IN_GGGA(X2, X1, .(X3, X4), X5)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
GA_IN_GGGA(x1, x2, x3, x4)  =  GA_IN_GGGA(x1, x2, x3)

We have to consider all (P,R,Pi)-chains

(8) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(9) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GA_IN_GGGA(.(X1, X2), X3, X4) → GA_IN_GGGA(X2, X1, .(X3, X4))

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(10) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

• GA_IN_GGGA(.(X1, X2), X3, X4) → GA_IN_GGGA(X2, X1, .(X3, X4))
  The graph contains the following edges 1 > 1, 1 > 2

(11) YES

(12) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5)), X6) → FC_IN_GGA(.(X4, .(X3, .(X1, X2))), X5, X6)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
FC_IN_GGA(x1, x2, x3)  =  FC_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains

(13) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(14) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5))) → FC_IN_GGA(.(X4, .(X3, .(X1, X2))), X5)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(15) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

• FC_IN_GGA(.(X1, X2), .(X3, .(X4, X5))) → FC_IN_GGA(.(X4, .(X3, .(X1, X2))), X5)
  The graph contains the following edges 2 > 2

(16) YES